import random
import time


class Sort:
    def __init__(self, n):
        self.len = n
        # [27, 87, 32, 94, 84, 42, 14, 25, 48, 17]
        self.arr = [0] * n  # 这个表达式会创建一个包含 n 个元素的列表，每个元素的值都是 0
        self.random_data()  # 使用随机数生成列表

    def random_data(self):
        for i in range(self.len):
            self.arr[i] = random.randint(0, 99)

    def Partition_one(self, left, right):
        """
        快排的划分函数
        """
        pivot = self.arr[left]
        while left < right:
            while left < right and self.arr[right] > pivot:
                right -= 1
            self.arr[left] = self.arr[right]
            while left < right and self.arr[left] <= pivot:
                left += 1
            self.arr[right] = self.arr[left]
        self.arr[left] = pivot
        return left

    def quick_sort(self, left, right):
        """
        快排的递归实现
        """
        if left < right:
            pos = self.Partition_one(left, right)
            self.quick_sort(left, pos - 1)
            self.quick_sort(pos + 1, right)

    def heap_adjust(self, pos, n):
        parent = pos
        son = 2 * pos + 1
        while son < n:
            if son + 1 >= n or self.arr[son + 1] < self.arr[son]:
                m_pos = son
            else:
                m_pos = son + 1
            if self.arr[parent] < self.arr[m_pos]:
                self.arr[parent], self.arr[m_pos] = self.arr[m_pos], self.arr[parent]
                parent = m_pos
                son = 2 * parent + 1
            else:
                return

    def heap_sort(self):
        i = self.len // 2
        while i >= 0:
            self.heap_adjust(i, self.len)
            i -= 1
        self.arr[0], self.arr[self.len - 1] = self.arr[self.len - 1], self.arr[0]
        n = self.len - 1
        while n > 1:
            self.heap_adjust(0, n)
            self.arr[0], self.arr[n - 1] = self.arr[n - 1], self.arr[0]
            n -= 1

    def test_time_use(self, sort_func, *args, **kwargs):
        """
        sort_func是代测试函数，*args,**kwargs是其可能会用到的参数
        """
        start = time.time()
        sort_func(*args, **kwargs)
        end = time.time()
        print(f"总耗时{end - start}")


if __name__ == '__main__':
    my_sort = Sort(10)
    print(my_sort.arr)
    my_sort.quick_sort(0, my_sort.len - 1)
    print(my_sort.arr)

    new_sort = Sort(10)
    print(new_sort.arr)
    new_sort.heap_sort()
    print(new_sort.arr)
